package algorithms.roughgarden.part2.primmst;


import java.util.ArrayList;
import java.util.List;

import com.notion.algorithms.datastructures.MinHeapAdapter;

public class Graph {

	private Vertex[] vertices;
	private short noOfVertices;
	private MinHeapAdapter<Edge> heap;
	private List<Edge> mst = new ArrayList<Edge>();;

	public Graph(short noOfVertices, short noOfEdges){
		this.noOfVertices = noOfVertices;
		vertices = new Vertex[noOfVertices];
		heap = new MinHeapAdapter<Edge>(noOfEdges);
		for(short i=0;i<noOfVertices;i++){
			vertices[i] = new Vertex(i);
		}		
	}
	public void addEdgeWithWeight(short vertexNo1, short vertexNo2, int weight){
		Vertex vertex1 = getVertexNumber(vertexNo1);
		Vertex vertex2 = getVertexNumber(vertexNo2);
		Edge edge = new Edge(getVertexNumber(vertexNo1), getVertexNumber(vertexNo2), weight);
		vertex1.addEdge(edge);
		vertex2.addEdge(edge);
	}
	private Vertex getVertexNumber(int vertexNumber){
		return vertices[vertexNumber-1];
	}
	public List<Edge> calculateMst(){
		Vertex sourceVertex = getVertexNumber(1);
		Vertex latestConsumedVertex;
		sourceVertex.setConsumedInMst(true);
		for(Edge e:sourceVertex.getEdgeList()){
			if(e.isCrossingEdge()){
				heap.insert(e);
			}
		}
		Edge minCrossingEdge;
		while(true){
			minCrossingEdge = heap.extractMin();
			//System.out.println(minCrossingEdge);
			while(minCrossingEdge!=null && !minCrossingEdge.isCrossingEdge()){
				minCrossingEdge = heap.extractMin();
				//System.out.println(minCrossingEdge);
			}
			if(null == minCrossingEdge)
				break;
			latestConsumedVertex = minCrossingEdge.getUnConsumedVertex();
			latestConsumedVertex.setConsumedInMst(true);
			for(Edge e:latestConsumedVertex.getEdgeList()){
				if(e.isCrossingEdge()){
					heap.insert(e);
				}
			}
			mst.add(minCrossingEdge);
		}

		return mst;
	}
}

class Vertex{
	private int value;
	private boolean isConsumedInMst;
	private List<Edge> edgeList = new ArrayList<Edge>();

	public Vertex(int value){
		this.value = value;
	}

	public boolean isConsumedInMst() {
		return isConsumedInMst;
	}

	public void setConsumedInMst(boolean isConsumedInMst) {
		this.isConsumedInMst = isConsumedInMst;
	}


	public int getValue() {
		return value;
	}

	public void addEdge(Edge edge){
		edgeList.add(edge);
	}

	public List<Edge> getEdgeList() {
		return edgeList;
	}

	@Override
	public boolean equals(Object obj) {
		Vertex v = (Vertex)obj;		
		return v.getValue()==this.getValue();
	}
	@Override
	public String toString() {
		return Integer.toString(this.getValue());
	}

}
class Edge implements Comparable<Edge>{
	private final Vertex vertex1;
	private final Vertex vertex2;
	private final int weight;

	public Edge(Vertex vertex1, Vertex vertex2, int weight){
		this.vertex1 = vertex1;
		this.vertex2 = vertex2;
		this.weight = weight;
	}

	public Vertex getVertex1() {
		return vertex1;
	}

	public Vertex getVertex2() {
		return vertex2;
	}

	public int getWeight() {
		return weight;
	}
	public boolean isCrossingEdge(){
		return vertex1.isConsumedInMst()^vertex2.isConsumedInMst();
	}
	public Vertex getUnConsumedVertex(){
		if(!isCrossingEdge()){
			return null;
		}
		else if(!vertex1.isConsumedInMst()){
			return vertex1;
		}
		else{
			return vertex2;
		}
	}

	@Override
	public boolean equals(Object obj) {
		Edge e = (Edge)obj;

		return ((e.getVertex1().equals(this.getVertex1()) && e.getVertex2().equals(this.getVertex2())) ||
				(e.getVertex1().equals(this.getVertex2()) && e.getVertex2().equals(this.getVertex1())));
	}

	public int compareTo(Edge o) {		
		return this.getWeight()-o.getWeight();
	}
	@Override
	public String toString() {
		return "("+vertex1.toString()+","+vertex2.toString()+","+weight+")";
	}
}
